/*
 *  linux/fs/bitmap.c
 *
 *  (C) 1991  Linus Torvalds
 */

/* bitmap.c contains the code that handles the inode and block bitmaps */
/* bitmap.c 程序含有处理 i 节点和磁盘逻辑块位图的代码 */
#include <string.h>

#include <linux/sched.h>
#include <linux/kernel.h>

// 将指定地址（addr）处的内存块(1K)清零。
// 输入：eax = 0； ecx = 以长字为单位的数据块长度 (BLOCK SIZE/4) edi =指定起始地址 addr。
#define clear_block(addr) \
__asm__ __volatile__ ("cld\n\t" \
	"rep\n\t" \
	"stosl" \
	::"a" (0),"c" (BLOCK_SIZE/4),"D" ((long) (addr)))

// 把指定地址addr开始的第 nr 个比特位置位。返回原比特位值。
// 输入：%0 -eax（返回值）；%1 -eax (0)；%2-nr，位偏移值（nr可大于32）；%3-(addr)，addr 的内容。
// 指令 btsl 用于测试并设置比特位 (Bit Test and Set)。把基地址（%3）和比特位偏移值（%2）所指定的比特位值先保存到进位标志 CF 中，然后设置该比特位为1。
// 指令 setb 用于根据进位标志 CF 设置操作数（%al）。如果 CF=1，则%al =1，否则%al =0。
#define set_bit(nr,addr) ({\
register int res ; \
__asm__ __volatile__("btsl %2,%3\n\tsetb %%al": \
"=a" (res):"0" (0),"r" (nr),"m" (*(addr))); \
res;})

//复位指定地址开始的第 nr 位偏移处的比特位。返回原比特位值的反码。
// 输入：%0 -eax（返回值）；%1 -eax(0)；%2-nr，位偏移值；%3 -(addr)，addr 的内容。
// 第27 行上的 btrl指令用于测试并复位比特位 (Bit Test and Reset）。其作用与上面的 btsl类似，但是复位指定比特位。
// 指令 setnb 用于根据进位标志 CF 设置操作数 (%a1） 如果 CF =1 则%al = 0，否则%al = 1。
#define clear_bit(nr,addr) ({\
register int res ; \
__asm__ __volatile__("btrl %2,%3\n\tsetnb %%al": \
"=a" (res):"0" (0),"r" (nr),"m" (*(addr))); \
res;})

// 从addr处开始寻找第1个0值比特位，返回比特位偏移值。共扫描8192个比特位（1KB）。
// 输入：%0 - ecx(返回值）；%1 - ecx (0)； %2 - esi (addr)。
// 返回值：比特位偏移值（从0开始，如果找到，返回值为0~8191；如果未找到，则返回8192）。
// addr 是位图缓冲块数据区的地址，扫描寻找的范围是1024字节（1块、1K、8192 比特位）。
#define find_first_zero(addr) ({ \
int __res; \
__asm__ __volatile__ ("cld\n" \
/* DS:ESI --> [eax]   */						"1:\tlodsl\n\t" \
/* 对eax取反           */ 	 					 "notl %%eax\n\t" \
/* 找到比特位为1 的位号edx */					   "bsfl %%eax,%%edx\n\t" \
/*                    */						"je 2f\n\t" \
/* 如果找到了			 */						 "addl %%edx,%%ecx\n\t" \
/*                    */						"jmp 3f\n" \
/* 未找到0值位，则将 ecx 加1个长字的位偏移量32 */	  "2:\taddl $32,%%ecx\n\t" \
/* 如果扫描累计不到 8192 比特位，调整1: 继续扫描*/ 	  "cmpl $8192,%%ecx\n\t" \
/*                    */						"jl 1b\n" \
/* 找到了 0值比特位 或 累计扫描达到8192个比特  */    "3:" \
/*                    */				 		:"=c" (__res):"c" (0),"S" (addr)); \
__res;})

// 释放设备dev上盘块block对应的bh，并复位对应的逻辑块位图比特位。（注意该函数不会处理脏数据落盘）
// 参数：dev - 设备号，block - 盘块号 （是逻辑块号，注意不是数据逻辑块号）。
void free_block(int dev, int block)
{
	struct super_block * sb;
	struct buffer_head * bh;

	if (!(sb = get_super(dev)))
		panic("trying to free block on nonexistent device");
	if (block < sb->s_firstdatazone || block >= sb->s_nzones)
		panic("trying to free block not in datazone");
	

	bh = get_hash_table(dev,block);
	// 然后从 hash 表中寻找该块数据。若找到了则判断其有效性，并清已修改和更新标志，释放该数据块。
	// 该段代码的主要用途是：如果该逻辑块目前存在于高速缓冲区中，就释放对应的缓冲块。
	/*
	注意下面这段程序（L56--66）有问题，会造成数据块不能释放。
	因为当 b_count > 1时， 这段代码会仅打印一段信息而没有执行释放操作。应作如下改动较合适：参加书籍551页
		if (bh->b_count > 1) {	// 若b_count > 1
			brelse(bh);			// b_count--后即退出，该块还有人用。
			return;
		}
		// 若此时 b_count 为1，则调用 brelse()释放之。
		bh->b_dirt=0;
		bh->b_uptodate=0;
		if (bh->b_count)
			brelse(bh);
	*/
	if (bh) {
		// free的快必须是bh->b_count为1
		if (bh->b_count != 1) {
			printk("trying to free block (%04x:%d), count=%d\n",
				dev,block,bh->b_count);
			return;
		}
		bh->b_dirt=0;
		bh->b_uptodate=0;
		// 释放引用次数（由1变成0）
		brelse(bh);
	}
	// 接着我们复位 block 在逻辑块位图中的比特位（置0）。
	/*
	先计算 block 在数据区开始算起的数据逻辑块号（从1开始计数）。
	然后对逻辑块(区块）位图进行操作，复位对应的比特位。
	如果对应比特位原来就是0，则出错停机。
	由于1个缓冲块有1024字节，即8192 比特位， 因此 block/8192 即可计算出指定块 block 在逻辑位图中的哪个块上。
	而 block&8191可以得到block 在逻辑块位图当前块中的比特偏移位置。
	*/
	// 将盘块号block转换为数据区的逻辑块块号（盘块从0开始编号；逻辑块从1开始编号）
	block -= sb->s_firstdatazone - 1 ;
	if (clear_bit(block&8191,sb->s_zmap[block/8192]->b_data)) {
		printk("block (%04x:%d) ",dev,block+sb->s_firstdatazone-1);
		panic("free_block: bit already cleared");
	}
	// 因更新了位图块，设置脏位
	sb->s_zmap[block/8192]->b_dirt = 1;
}

// 向设备申请一个未使用的新逻辑块（块号）。（在逻辑块位图中寻找0值比特位进行置位，然后获取逻辑块对应缓冲块并清零；）
// 实现：
// 		首先取得设备的超级块，并在超级块中的逻辑块位图中寻找第一个0值比特位（代表一个空闲逻辑块）。
// 		然后置位对应逻辑块在逻辑块位图中的比特位。接着为该逻辑块在缓冲区中取得一块对应缓冲块getblk()。
// 		最后将该缓冲块清零，并设置其己更新标志和己修改标志。并返回逻辑块号。
// 返回值：
// 函数执行成功则返回盘块号，否则返回0。
int new_block(int dev)
{
	struct buffer_head * bh;
	struct super_block * sb;
	int i,j;

	if (!(sb = get_super(dev)))
		panic("trying to get new block from nonexistant device");
	
	// 查找第1个未使用的逻辑块编号：即第i个位图块中j偏移
	j = 8192; 	// 8192为一个无效值
	for (i=0 ; i<8 ; i++)
		if ((bh=sb->s_zmap[i]))
			if ((j=find_first_zero(bh->b_data))<8192)
				break;
	if (i>=8 || !bh || j>=8192)
		return 0;
	// 设置位图比特位为1
	if (set_bit(j,bh->b_data))
		panic("new_block: bit already set");
	// 设置位图块脏标志
	bh->b_dirt = 1;
	// 将第（i+1）个位图中的数据逻辑块偏移值j 转换为全局编号的磁盘块号
	j += i*8192 + sb->s_firstdatazone-1;
	if (j >= sb->s_nzones)
		return 0;
	// 获取bh
	if (!(bh=getblk(dev,j)))
		panic("new_block: cannot get block");
	if (bh->b_count != 1)
		panic("new block: count is != 1");
	// 逻辑块对应的缓冲区块清零
	clear_block(bh->b_data);
	// 因clear_block把buffer逻辑块清零，所以需要设置为dirty。
	bh->b_uptodate = 1;
	bh->b_dirt = 1;
	brelse(bh);
	return j;
}

// 释放指定的i节点（清空i节点结构）
void free_inode(struct m_inode * inode)
{
	struct super_block * sb;
	struct buffer_head * bh;

	if (!inode)
		return;
	// 如果i节点上的设备号字段为0，说明该节点没有使用。于是用0清空对应i节点所占内存区并返回。
	if (!inode->i_dev) {
		memset(inode,0,sizeof(*inode));
		return;
	}
	if (inode->i_count>1) {
		printk("trying to free inode with count=%d\n",inode->i_count);
		panic("free_inode");
	}
	if (inode->i_nlinks)
		panic("trying to free inode with links");
	if (!(sb = get_super(inode->i_dev)))
		panic("trying to free inode on nonexistent device");
	if (inode->i_num < 1 || inode->i_num > sb->s_ninodes)
		panic("trying to free inode 0 or nonexistant inode");
	if (!(bh=sb->s_imap[inode->i_num>>13]))
		panic("nonexistent imap in superblock");
	if (clear_bit(inode->i_num&8191,bh->b_data))
		printk("free_inode: bit already cleared.\n\r");
	bh->b_dirt = 1;
	memset(inode,0,sizeof(*inode));
}

// 为设备 dev建立一个新i节点。初始化并返回该新i节点的指针。
// 在内存i节点表中获取一个空闲i节点表项，并从i节点位图中找一个空闲i节点。
struct m_inode * new_inode(int dev)
{
	struct m_inode * inode;
	struct super_block * sb;
	struct buffer_head * bh;
	int i,j;

	// 获取一个indoe
	if (!(inode=get_empty_inode()))
		return NULL;
	// 从超级块中获取inode位图块
	if (!(sb = get_super(dev)))
		panic("new_inode with unknown device");
	
	// 从i节点位图中找一个空闲i节点
	j = 8192;
	for (i=0 ; i<8 ; i++)
		if ((bh=sb->s_imap[i]))
			if ((j=find_first_zero(bh->b_data))<8192)
				break;
	// 如果全部扫描完还没找到，或者位图所在的缓冲块无效(bh = NULL) 
	// 则放回先前申请的i节点表中的i节点，并返回空指针退出（没有空闲i节点)。
	if (!bh || j >= 8192 || j+i*8192 > sb->s_ninodes) {
		iput(inode);
		return NULL;
	}
	// 设置inode位图
	if (set_bit(j,bh->b_data))
		panic("new_inode: bit already set");
	bh->b_dirt = 1;		// inode位图块设置为脏块
	inode->i_count=1;
	inode->i_nlinks=1;
	inode->i_dev=dev;
	inode->i_uid=current->euid;
	inode->i_gid=current->egid;
	inode->i_dirt=1;	// 因inode更新，所以设置为脏数据
	inode->i_num = j + i*8192;
	inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
	return inode;
}
